#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list.h"

// Write all your functions here.

bool IsEmpty(Node* head) {
  // If the head node is NULL then the linked list is empty.
  return head == NULL;
}

Node* InsertNode(Node** phead, int index, double x) {
  if(index < 0) return NULL;

  // Try to locate the node at position index.
  // If it does not exist, return NULL.
  int currIndex = 1;
  Node* currNode = *phead;
  while(currNode != NULL && index > currIndex) {
    currNode = currNode->next;
    currIndex++;
  }
  if(index > 0 && currNode == NULL) return  NULL;

  // Create a new Node.
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = x;
  if(index == 0) {
    // Insert as the new head:
    newNode->next = *phead;
    *phead = newNode;
  } else {
    // Insert after currNode:
    newNode->next = currNode->next;
    currNode->next = newNode;
  }
  return newNode;
}

int FindNode(Node* head, double x) {
  Node* current = head;
  // Position counting starts from 1.
  int pos = 1;
  while(current != NULL) {
    if(current->data == x) {
      return pos;
    }
    pos++;
    current = current->next;
  }
  // We have reached the end of the list so the list does not contain x.
  return 0;
}

int DeleteNode(Node** phead, double x) {
  Node* current = *phead;
  Node* previous = NULL;
  // Position counting starts from 1.
  int pos = 1;
  while(current != NULL) {
    if(current->data == x) {
      // current now points at the node we want to delete.
      // First we remove that node from the list.
      if(previous == NULL) {
	// Removing the head node from the list:
	*phead = current->next;
      } else {
	// Removing a node in the middle or at the end of the list:
	previous->next = current->next;
      }
      // Then we delete the node and return its position:
      free(current);
      return pos;
    }
    // The current node is not the one we are looking for so we keep searching:
    pos++;
    previous = current;
    current = current->next;
  }
  // We have reached the end of the list so the list does not contain x.
  return 0;
}

void DisplayList(Node* head) {
  Node* current = head;
  while(current != NULL) {
    printf("%f ", current->data);
    current = current->next;
  }
  printf("\n");
}

void DestroyList(Node* head){
  Node* current = head;
  while(current != NULL) {
    Node* next = current->next;
    free(current);
    current = next;
  }
}

// Testing all the functions:
int main(void) {
  Node* head = NULL;

  // Output: true
  printf("%s\n", IsEmpty(head) ? "true" : "false");

  // Must output an empty line:
  DisplayList(head);

  // Must output "insert failed":
  Node* result = InsertNode(&head, 20, 7);
  printf("%s\n", result == NULL ? "insert failed" : "insert succeeded");

  // Output: 0.000000 1.000000 2.000000 3.000000 4.000000
  for(int i = 0; i < 5; i++) {
    InsertNode(&head, i, i);
  }
  DisplayList(head);

  // Output: false
  printf("%s\n", IsEmpty(head) ? "true" : "false");

  // Output: 4.000000 3.000000 2.000000 1.000000 0.000000 0.000000 1.000000 2.000000 3.000000 4.000000
  for(int i = 0; i < 5; i++) {
    InsertNode(&head, 0, i);
  }
  DisplayList(head);

  // Output: 0.000000 is at position 5
  //         2.000000 is at position 3
  //         4.000000 is at position 1
  //         6.000000 is not in the list
  for(int i = 0; i < 7; i += 2) {
    int idx = FindNode(head, i);
    if(idx > 0) {
      printf("%f is at position %d\n", (double)i, idx);
    } else {
      printf("%f is not in the list\n", (double)i);
    }
  }

  // Output: inserted 10.000000
  //         4.000000 3.000000 2.000000 10.000000 1.000000 0.000000 0.000000 1.000000 2.000000 3.000000 4.000000
  Node *in = InsertNode(&head, 3, 10);
  printf("inserted %f\n", in->data);
  DisplayList(head);

  // Output: 4.000000 3.000000 2.000000 10.000000 1.000000 0.000000 1.000000 2.000000 3.000000 4.000000
  //         3.000000 2.000000 10.000000 1.000000 0.000000 1.000000 2.000000 3.000000 4.000000
  //         3.000000 2.000000 10.000000 1.000000 0.000000 1.000000 2.000000 3.000000
  DeleteNode(&head, 0); // Delete in the middle of the list.
  DisplayList(head);
  DeleteNode(&head, 4); // Delete at the front of the list.
  DisplayList(head);
  DeleteNode(&head, 4); // Delete at the end of the list.
  DisplayList(head);

  DestroyList(head);

  return 0;
}
